# -*- coding=utf-8-*-
"""
@File:memory_selection
@Author:Created by Han X.Y
@Date:on 2021/8/4 18:19 
"""
"""
给你一个字符串 s，找到 s 中最长的回文子串。

 

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb"
示例 3：

输入：s = "a"
输出："a"
示例 4：

输入：s = "ac"
输出："a"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


"""


# class Solution:
#     def longestPalindrome(self, s):
#         if s==s[::-1]:
#             return s
#         else:
#             output = ""
#             output_len = 0
#             for i in range(1,len(s)):
#                 for j in range(len(s)-1):
#                     tmp=s[j:i]
#                     if tmp==tmp[::-1] and len(tmp)>output_len:
#                         output_len=len(tmp)
#                         output=tmp
#             return output



class Solution:
    def longestPalindrome(self, s):
        if s==s[::-1]:
            return s
        else:
            output = ""
            output_len = 0
            # i,j=0,1
            i=0
            """
            i:从0开始移动，while里面使用for循环；
            当最大回文子串的长度大于等于剩余字符串长度时，算法端停止
            
            """
            while  i<len(s) and len(s[i:])>output_len:
                tmp=s[i:]
                for  j in range(1,len(tmp)+1):
                    tmp_=tmp[:j]
                    if tmp_==tmp_[::-1] and len(tmp_)>output_len:
                        output_len=len(tmp_)
                        output=tmp_
                i+=1
            return output


if __name__=="__main__":
    s=Solution()
    for i in ["babad","cbbd","a","ac",'bb',"abb"]:
        print("main_output:",i,s.longestPalindrome(i))